'''
https://leetcode.cn/problems/shortest-subarray-with-sum-at-least-k/
'''
from collections import deque
from typing import List
class Solution:
    def shortestSubarray(self, nums: List[int], k: int) -> int:
        n = len(nums)
        ans = float('inf')
        pre_sum = [0] * (n + 1)
        for i in range(n):
            pre_sum[i + 1] = pre_sum[i] + nums[i]

        # sum[l,r] = pre_sum[r+1]-pre_sum[l]
        monotonic_q = deque()       # 从左往右，从小到大，
                                    # 当前窗口最小的元素在最左边
                                    # 以使得 presum[r]-presum[q[0]] 最大及q[0]~r范围内的累加和尽量大
        r = 0
        while r < n:
            while monotonic_q and pre_sum[r] < pre_sum[monotonic_q[-1]]:
                monotonic_q.pop()
            monotonic_q.append(r)

            while monotonic_q and pre_sum[r + 1] - pre_sum[monotonic_q[0]] >= k:
                ans = min(ans, r - monotonic_q.popleft() + 1)
            r += 1

        return ans if ans != float('inf') else -1